A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

Harmonic analysis on the Pascal graph

In this paper, we completely determine the spectral invariants of an auto-similar planar 3-regular graph. Using the same methods, we study the spectral invariants of a natural compactification of this graph.     

Bicyclic graphs with exactly two main eigenvalues

An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero, and it is well known that a graph has exactly one main eigenvalue if and only if it is regular. In this work, all connected bicyclic graphs with exactly two main eigenvalues are determined.     

A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs

Given an undirected graph G with penalties associated with its vertices and costs associated with its edges, a Prize Collecting Steiner (PCS) tree is either an isolated vertex of G or else any tree of G, be it spanning or not. The weight of a PCS tree equals the sum of the costs for its edges plus the sum of the penalties for the vertices of G not spanned by the PCS tree. Accordingly, the Prize Collecting Steiner Problem in Graphs (PCSPG) is to find a PCS tree with the lowest weight. In this paper, after reformulating and re-interpreting a given PCSPG formulation, we use a Lagrangian Non Delayed Relax and Cut (NDRC) algorithm to generate primal and dual bounds to the problem. The algorithm is capable of adequately dealing with the exponentially many candidate inequalities to dualize. It incorporates ingredients such as a new PCSPG reduction test, an effective Lagrangian heuristic and a modification in the NDRC framework that allows duality gaps to be further reduced. The Lagrangian heuristic suggested here dominates their PCSPG counterparts in the literature. The NDRC PCSPG lower bounds, most of the time, nearly matched the corresponding Linear Programming relaxation bounds.     

On cover-structure graphs

Motivated by a problem in communication complexity, we study cover-structure graphs (cs-graphs), defined as intersection graphs of maximal monochromatic rectangles in a matrix. We show that not every graph is a cs-graph. Especially, squares and odd holes are not cs-graphs.It is natural to look at graphs (beautiful graphs) having the property that each induced subgraph is a cs-graph. They form a new class of Berge graphs. We make progress towards their characterization by showing that every square-free bipartite graph is beautiful, and that beautiful line graphs of square-free bipartite graphs are just Path-or-Even-Cycle-of-Cliques graphs.     

An introduction to the perplex number system

The perplex number system is a generalization of the abstract logical relationships among electrical particles. The inferential logic of the new number system is homologous to the inferential logic of the progression of the atomic numbers. An electrical progression is defined categorically as a sequence of objects with teridentities. Each identity infers corresponding values of an integer, units and a correspondence relation between each unit and its integer. Thus, in this logical system, each perplex numeral contains an exact internal representational structure; it carries an internal message. This structure is a labeled bipartite graph that is homologous to the internal electrical structure of a chemical atom. The formal logical operations are conjunctions and disjunctions. Combinations of conjunctions and disjunctions compose the spatiality of objects. Conjunctions may include the middle term of pairs of propositions with a common term, thereby creating new information. The perplex numerals are used as a universal source of diagrams.The perplex number system, as an abstract generalization of concrete objects and processes, constitutes a new exact notation for chemistry without invoking alchemical symbols. Practical applications of the number system to concrete objects (chemical elements, simple ions and molecules, and the perplex isomers, ethanol and dimethyl ether) are given. In conjunction with the real number system, the relationships between the perplex number system and scientific theories of concrete systems (thermodynamics, intra-molecular dynamics, molecular biology and individual medicine) are described.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

NP-hardness of the recognition of coordinated graphs

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C ₄, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. F.J. Soulignac is partially supported by UBACyT Grant X184, Argentina and CNPq under PROSUL project Proc. 490333/2004-4, Brazil.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Minimum C5‐saturated graphs

A graph is C₅‐saturated if it has no five‐cycle as a subgraph, but does contain a C₅ after the addition of any new edge. We prove that the minimum number of edges in a C₅ ‐saturated graph on n≥11 vertices is sat(n, C₅)=?10(n?1)/7??1 if n∈N₀={11, 12, 13, 14, 16, 18, 20} and is ?10(n?1)/7? if n≥11 and n?N₀. © 2009 Wiley Periodicals, Inc. J Graph Theory